#include "sort.h"
#include<stack>
#include<utility>
#include <iostream>
using std::stack;
void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int max = end;
		int min = begin;
		for (int i = begin; i < end; i++)
		{
			if (a[i] > a[max])
			{
				max = i;
			}
			if (a[i] < a[min])
			{
				min = i;
			}
		}
		Swap(&a[begin], &a[min]);
		//极端情况最大值刚好在begin，交换后max的位置在原本的min的位置上
		if (max == begin)
		{
			max = min;
		}
		Swap(&a[end], &a[max]);
		begin++;
		end--;

	}
}
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end--)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

void ShellSort(int* a, int n)
{ 
	int gap = n;
	while (gap>1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		 }
	}
}
void AdjustDown(int* a, int n, int root) {
	int parent = root;
	int child = 2 * parent + 1; // 左孩子

	while (child < n) {
		// 选择左右孩子中较大的一个
		if (child + 1 < n && a[child + 1] > a[child]) {
			child++;
		}

		// 如果孩子大于父节点，交换并继续向下调整
		if (a[child] > a[parent]) {
			int temp = a[parent];
			a[parent] = a[child];
			a[child] = temp;

			parent = child;
			child = 2 * parent + 1;
		}
		else {
			break; // 调整完成
		}
	}
}

// 堆排序主函数
void HeapSort(int* a, int n) {
	// 1. 构建大顶堆（从最后一个非叶子节点开始）
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
		AdjustDown(a, n, i);
	}

	// 2. 逐个取出堆顶元素（最大值）并调整堆
	for (int i = n - 1; i > 0; i--) {
		// 将堆顶元素（最大值）与当前未排序部分的最后一个元素交换
		int temp = a[0];
		a[0] = a[i];
		a[i] = temp;

		// 对剩余元素重新调整为大顶堆
		AdjustDown(a, i, 0);
	}
}

void BubbleSort(int* a, int n)
{
	int flag;
	for (int i = 0; i < n-1; i++)
	{
		flag = 0;
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;
		}

	}
}

int PartSort1(int* a, int left, int right)    
{
	if (left >= right)
	{
		return;
	}
	int start = left;
	int end = right;
	int key = a[left];
	while (left < right)
	{
		while (a[right] > key && left < right)  //让右边先走，确保left和right相遇的时候的值小于key
		{
			right--;
		}
		while (a[left] < key&&left<right)
		{
			left++;
		}
		if (left < right)
		{
			Swap(&a[left], &a[right]);
		}
     
	}
	Swap(&a[start], &a[left]);
	PartSort1(a, start,left-1);
	PartSort1(a, left + 1, end);
	return left;
}

int PartSort2(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int start = left;
	int end = right;
	int key = a[left];
	int index = left;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[index] = a[right];
		index = right;
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[index] = a[left];
		index = left;
	}
	a[index] = key;
	PartSort2(a, start, left - 1);
	PartSort2(a, left + 1, end);
	return left;
	
}

int PartSort3(int* a, int left, int right)
{
	if (left >= right)
	{
		return left;
	}
	int start = left;
	int end = right;
	int key = a[left];
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (cur<=right&&a[cur] < key)
		{
			prev++;
			if (prev != cur)
			{
				Swap(&a[prev], &a[cur]);
			}
		}
		cur++;
	}
	Swap(&a[start], &a[prev]);
	return prev;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = PartSort3(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

void QuickSortNonR(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	stack<int> st;
	st.push(right);
	st.push(left);
	while (!st.empty())
	{
		int start = st.top();
		st.pop();
		int end = st.top();
		st.pop();
		int keyi = PartSort1(a, start, end);
		if (keyi - 1 > start)
		{
			st.push(keyi - 1);
			st.push(start);
		}
		if (keyi + 1 < end)
		{
			st.push(end);
			st.push(keyi + 1);
		}
	}
}
void QuickSortadd1(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;
	int keyi = left + (rand() % (right - left + 1));
	Swap(&a[left], &a[keyi]);
	int cur = left + 1;
	int key = a[left];
	while (cur <= right)
	{
		if (a[cur] < key)
		{
			Swap(&a[cur], &a[left]);
			cur++;
			left++;
		}
		else if (a[cur] > key)
		{
			Swap(&a[cur], &a[right]);
			right--;
		}
		else
		{
			cur++;
		}
	}
	QuickSortadd1(a, begin, left - 1);
	QuickSortadd1(a, right + 1, end);

}
void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
{
	if (left >= right)
	{
		return;
	}
	if (right - left + 1 < 16)
	{
		InsertSort(a + left, right - left + 1);
		return;
	}
	if (depth > defaultDepth)
	{
		HeapSort(a + left, right - left + 1);
		return;
	}
	depth++;
	int begin = left;
	int end = right;
	// 随机选key
	int randi = left + (rand() % (right - left));
	Swap(&a[left], &a[randi]);
	int prev = left;
	int cur = prev + 1;
	int keyi = left;

	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	// [begin, keyi-1] keyi [keyi+1, end]
	IntroSort(a, begin, keyi - 1, depth, defaultDepth);
	IntroSort(a, keyi + 1, end, depth, defaultDepth);


}
void QuickSortadd2(int* a, int left, int right)
{
	int depth = 0;
	int logn = 0;
	int N = right - left + 1;
	for (int i = 1; i < N; i *= 2)
	{
		logn++;
	}
	IntroSort(a, left, right, depth, 2 * logn);
}
void _MergeSort(int* a, int* tmp, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;
	_MergeSort(a, tmp, begin, mid);
	_MergeSort(a, tmp, mid + 1, end);
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

void MergeSort(int* a, int n)
{
	int* ptr = new int[n];
	if (ptr == nullptr)
	{
		return;
	}
	_MergeSort(a, ptr, 0, n - 1);
	delete[]ptr;
	ptr = nullptr;
}

void MergeSortNonR(int* a, int n)
{
	int* tmp = new int[n];
	if (tmp == nullptr)
	{
		return;
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap-1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			int index = i;
			if (begin1 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}
			memcpy(a + index, tmp + i, (end2 - i + 1) * sizeof(int));
		}
		gap *= 2;
	}
	delete[]tmp;
	tmp = nullptr;
}
